package bfs;

public class 迷宫的最近出口 {
	public static int l,r;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public static int MAXM=101,MAXN=101;
    public static int[][] queue=new int[MAXM*MAXN][2];
    public static boolean[][] visit;
    public int nearestExit(char[][] maze, int[] entrance) {
        int m=maze.length,n=maze[0].length;
        int p=entrance[0],q=entrance[1];
        visit=new boolean[MAXM][MAXN];
        l=r=0;
        int ret=0;
        queue[r][0]=p;
        queue[r++][1]=q;
        visit[p][q]=true;
        //bfs
        while(l<r){
            int size=r-l;
            ret++;
            for(int i=0;i<size;i++){
                int nx=queue[l][0],ny=queue[l++][1];
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]==false&&maze[x][y]=='.'){
                        //判断是否到出口
                    	if((x==0||y==0||x==m-1||y==n-1)){
                            return ret;
                        }
                        queue[r][0]=x;
                        queue[r++][1]=y;
                        visit[x][y]=true;
                    }
                }
            }
        }
        //如果能到出口，一定会因为上面的语句返回，到这，说明一定无法到出口；
        return -1;
    }
}
